#include "BigInteger.h"
#include <memory>


using namespace std;

namespace BigIntegerUtils
  {
  
unique_ptr<vector<int>> add(const vector<int>& i_first, const vector<int>& i_second, int i_base = 10)
  {
  // getting sizes
  size_t sz1 = i_first.size();
  size_t sz2 = i_second.size();
  size_t max_sz = (sz1 >= sz2 ? sz1 : sz2);
  size_t min_sz = (sz1 <= sz2 ? sz1 : sz2);

  // creating result vector
  vector<int> res;
  res.reserve(max_sz + 1);
  
  int over = 0; // overflow
  for (size_t p = 0; p < max_sz; ++p)
    {
    if (p >= sz1)
      res.push_back(i_second[p] + over);
    else if (p >= sz2)
      res.push_back(i_first[p] + over);
    else
      res.push_back(i_first[p] + i_second[p] + over);
    over = 0;
    if (res[p] >= i_base)
      {
      over = res[p] / i_base;
      res[p] -= i_base;
      }
    }
  if (over > 0)
    res.push_back(over);
  auto res_ptr = make_unique<decltype(res)>(res);
  return res_ptr;
  }

// assuming first argument is greater than second
unique_ptr<vector<int>> subtract(const vector<int>& i_first, const vector<int>& i_second, int i_base = 10)
  {
  // getting sizes
  size_t sz1 = i_first.size();
  size_t sz2 = i_second.size();
  size_t max_sz = (sz1 >= sz2 ? sz1 : sz2);
  size_t min_sz = (sz1 <= sz2 ? sz1 : sz2);

  // creating result vector
  vector<int> res(max_sz + 1);
  for (size_t p = 0; p < sz1; ++p)
    res[p] = i_first[p];

  for (size_t p = 0; p < sz2; ++p)
    {
    res[p] -= i_second[p];
    if (res[p] < 0)
      {
      res[p] += i_base;
      try
        {
        --res[p + 1];
        }
      catch (std::out_of_range)
        {
        throw std::invalid_argument("subtraction");
        }
      }
    }
  for (size_t p = res.size() - 1; p > 0; --p)
    {
    if (res[p] != 0)
      break;
    res.pop_back();
    }
  auto res_ptr = make_unique<decltype(res)>(res);
  return res_ptr;
  }

unique_ptr<vector<int>> split(const vector<int>& i_arg, size_t i_lo, size_t i_hi)
  {
  vector<int> res;
  res.reserve(i_hi - i_lo);
  for (size_t p = i_lo; p < i_hi; ++p)
    res.push_back(i_arg[p]);
  return make_unique<decltype(res)>(res);
  }

unique_ptr<vector<int>> multiply(const vector<int>& i_vec, int i_scalar, int i_base)
  {
  vector<int> res;
  res.reserve(i_vec.size() + 1);

  int over = 0;
  for (size_t p = 0; p < i_vec.size(); ++p)
    {
    res.push_back(i_vec[p] * i_scalar + over);
    over = 0;
    if (res[p] >= i_base)
      {
      over = res[p] / i_base;
      res[p] %= i_base;
      }
    }
  if (over > 0)
    res.push_back(over);
  return make_unique<decltype(res)>(res);
  }

unique_ptr<vector<int>> multiply(const vector<int>& i_first, const vector<int>& i_second, int i_base = 10)
  {
  // getting sizes
  size_t sz1 = i_first.size();
  size_t sz2 = i_second.size();
  size_t max_sz = (sz1 >= sz2 ? sz1 : sz2);
  size_t min_sz = (sz1 <= sz2 ? sz1 : sz2);

  if (sz2 == 1)
    {
    return multiply(i_first, i_second[0], i_base);
    }
  else if (sz1 == 1)
    {
    return multiply(i_second, i_first[0], i_base);
    }

  // creating result vector
  vector<int> res;

  size_t m2 = static_cast<size_t>(ceil((double)max_sz / 2));
  
  vector<int> lo1, hi1, lo2, hi2;
  swap(lo1, *split(i_first, 0, m2));
  swap(hi1, *split(i_first, m2, sz1));
  swap(lo2, *split(i_second, 0, m2));
  swap(hi2, *split(i_second, m2, sz2));

  auto z0 = *multiply(lo1, lo2, i_base);
  auto z2 = *multiply(hi1, hi1, i_base);
  auto z1 = *multiply(*add(lo1, hi1, i_base), *add(lo2, hi2, i_base));
  
  // here: res = (z2 * 10 ^ (2 * m2)) + ((z1 - z2 - z0) * 10 ^ (m2)) + (z0)
  auto tmp = *subtract(*subtract(z1, z2, i_base), z0, i_base);
  
  // slide z2
  z2.reserve(z2.size() + 2 * m2);
  for (size_t i = 0; i < 2 * m2; ++i)
    z2.push_back(0);

  // slide tmp
  tmp.reserve(tmp.size() + m2);
  for (size_t i = 0; i < m2; ++i)
    tmp.push_back(0);

  // result
  auto p_res = add(*add(z2, tmp, i_base), z0);

  return p_res;
  }
  }

BigInteger::BigInteger()
  {
  m_digits = vector<int>();
  m_digits.reserve(m_append_lenght);
  }

BigInteger::BigInteger(const BigInteger& i_other)
  {
  m_digits = i_other.m_digits;
  m_sign = i_other.m_sign;
  }


BigInteger::BigInteger(BigInteger&& i_other)
: BigInteger()
  {
  _Swap(i_other);
  }


BigInteger& BigInteger::operator=(BigInteger i_other)
  {
  _Swap(i_other);
  return *this;
  }

BigInteger::BigInteger(long long i_number)
  {
  m_digits = vector<int>();
  m_digits.reserve(20);
  
  // setting sign
  if (i_number > 0)
    m_sign = 1;
  else if (i_number == 0)
    {
    m_sign = 1;
    m_digits.push_back(0);
    return;
    }
  else // if (i_number < 0)
    {
    m_sign = -1;
    i_number *= -1;
    }
  // setting digits
  size_t pos = 0;
  while (i_number)
    {
    unsigned short d = i_number % m_number_base;
    m_digits.push_back(d);
    ++pos;
    i_number /= m_number_base;
    }
  }

BigInteger::BigInteger(const std::string& i_str_number )
  {
  if (i_str_number.empty())
    throw invalid_argument("empty string");

  size_t cur_pos = 0;
  if (i_str_number[cur_pos] == '-')
    {
    m_sign = -1;
    ++cur_pos;
    }

  m_digits = vector<int>();
  m_digits.reserve(20);

  size_t str_lng = i_str_number.size();
  short digit = 0;
  bool null_prefix = true;
  for (; cur_pos < str_lng; ++cur_pos)
    {
    digit = i_str_number[cur_pos] - '0';
    if (digit < 0 || digit > 9)
      throw invalid_argument(i_str_number);
    if (digit != 0)
      null_prefix = false;
    if (!null_prefix)
      m_digits.push_back(digit);
    }
  if (m_digits.size() == 0)
    m_digits.push_back(0);
  reverse(m_digits.begin(), m_digits.end());
  
  if (m_sign != -1)
    {
    if (*this == 0)
      m_sign = 0;
    else
      m_sign = 1;
    }
  }

BigInteger::~BigInteger()
  {

  }

string BigInteger::ToString() const
  {
  string res(m_digits.size(), '0');
  for (size_t p = 0; p < m_digits.size(); ++p)
    res[p] = m_digits[p] + '0';
  return res;
  }



BigInteger& BigInteger::operator+=(const BigInteger& i_other)
  {
  if (m_sign > 0 && i_other.m_sign > 0)
    {
    swap(m_digits, *(BigIntegerUtils::add(m_digits, i_other.m_digits, m_number_base)));
    }
  else if (m_sign > 0 && i_other.m_sign < 0)
    {
    m_sign = - 1;
    if (*this < i_other)
      {
      swap(m_digits, *(BigIntegerUtils::subtract(m_digits, i_other.m_digits, m_number_base)));
      m_sign = 1;
      }
    else
      {
      swap(m_digits, *(BigIntegerUtils::subtract(i_other.m_digits, m_digits, m_number_base)));
      }
    }
  else if (m_sign < 0 && i_other.m_sign > 0)
    {
    m_sign = 1;
    if (*this >= i_other)
      {
      swap(m_digits, *(BigIntegerUtils::subtract(m_digits, i_other.m_digits, m_number_base)));
      m_sign = -1;
      }
    else
      {
      swap(m_digits, *(BigIntegerUtils::subtract(i_other.m_digits, m_digits, m_number_base)));
      m_sign = 1;
      }
    }
  else // if (m_sign < 0 && i_other.m_sign < 0)
    {
    swap(m_digits, *(BigIntegerUtils::add(m_digits, i_other.m_digits, m_number_base)));
    }
  return *this;
  }

BigInteger& BigInteger::operator-=(const BigInteger& i_other)
  {
  if (m_sign > 0 && i_other.m_sign > 0)
    {
    if (*this >= i_other)
      {
      swap(m_digits, *(BigIntegerUtils::subtract(m_digits, i_other.m_digits, m_number_base)));
      }
    else
      {
      swap(m_digits, *(BigIntegerUtils::subtract(i_other.m_digits, m_digits, m_number_base)));
      m_sign = -1;
      }
    }
  else if (m_sign > 0 && i_other.m_sign < 0)
    {
    swap(m_digits, *(BigIntegerUtils::add(i_other.m_digits, m_digits, m_number_base)));
    }
  else if (m_sign < 0 && i_other.m_sign > 0)
    {
    swap(m_digits, *(BigIntegerUtils::add(i_other.m_digits, m_digits, m_number_base)));
    }
  else // if (m_sign < 0 && i_other.m_sign < 0)
    {
    if (*this >= i_other)
      {
      swap(m_digits, *(BigIntegerUtils::subtract(i_other.m_digits, m_digits, m_number_base)));
      m_sign = 1;
      }
    else
      {
      swap(m_digits, *(BigIntegerUtils::subtract(m_digits, i_other.m_digits, m_number_base)));
      }
    }

  return *this;
  }

BigInteger& BigInteger::operator*=(const BigInteger& i_other)
  {
  BigInteger res = 0;
  BigInteger i = 0;
  for (; i < i_other; ++i)
    res += *this;
  swap(res, *this);
  return *this;
  }

BigInteger& BigInteger::operator/=(const BigInteger& i_other)
  {
  BigInteger res = 0;
  while (*this > 0)
    {
    *this -= i_other;
    ++res;
    }
  swap(res, *this);
  return *this;
  }

BigInteger& BigInteger::operator++()
  {
  *this += 1;
  return *this;
  }

BigInteger  BigInteger::operator++(int)
  {
  BigInteger tmp = *this;
  *this += 1;
  return tmp;
  }

BigInteger& BigInteger::operator--()
  {
  *this -= 1;
  return *this;
  }

BigInteger  BigInteger::operator--(int)
  {
  BigInteger tmp = *this;
  *this += 1;
  return tmp;
  }

BigInteger BigInteger::operator-() const
  {
  BigInteger res(*this);
  res.m_sign *= -1;
  return move(res);
  }

BigInteger BigInteger::operator+() const
  {
  BigInteger res = *this;
  return move(res);
  }


// getter functions
size_t BigInteger::GetDigitNumber() const
  {
  return m_digits.size();
  }

unsigned short BigInteger::GetDigit(size_t i_position) const
  {
  return m_digits[i_position];
  }

bool BigInteger::IsPositive() const
  {
  return m_sign > 0;
  }

bool BigInteger::IsNegative() const
  {
  return m_sign < 0;
  }

// iostream operators overloading
std::ostream& operator<<(std::ostream& i_ostream, const BigInteger& i_number)
  {
  if (i_number.IsNegative())
    i_ostream << '-';
  
  size_t digit_number = i_number.GetDigitNumber();
  for (size_t pos = 0; pos < digit_number; ++pos)
    {
    i_ostream << i_number.GetDigit(digit_number - 1 - pos);
    }
  
  return i_ostream;
  }

std::istream& operator>>(std::istream& i_istream, BigInteger& o_number)
  {
  string input;
  i_istream >> input;
  o_number = BigInteger(input);
  return i_istream;
  }

// binary arithmetic operators overloading
BigInteger operator+(BigInteger i_number_left, const BigInteger& i_number_right)
  {
  i_number_left += i_number_right;
  return i_number_left;
  }

BigInteger operator-(BigInteger i_number_left, const BigInteger& i_number_right)
  {
  i_number_left -= i_number_right;
  return i_number_left;
  }

BigInteger operator*(BigInteger i_number_left, const BigInteger& i_number_right)
  {
  i_number_left *= i_number_right;
  return move(i_number_left);
  }

BigInteger operator/(BigInteger i_number_left, const BigInteger& i_number_right)
  {
  i_number_left /= i_number_right;
  return move(i_number_left);
  }

// compare operators overloading
bool operator==(const BigInteger& i_number_left, const BigInteger& i_number_right)
  {
  if (i_number_left.GetDigitNumber() != i_number_right.GetDigitNumber())
    return false;

  if (i_number_left.IsPositive() != i_number_right.IsPositive())
    return false;

  for (size_t i = 0; i < i_number_left.GetDigitNumber(); ++i)
    {
    if (i_number_left.GetDigit(i) != i_number_right.GetDigit(i))
      return false;
    }

  return true;
  }

bool operator!=(const BigInteger& i_number_left, const BigInteger& i_number_right)
  {
  return !(i_number_left == i_number_right);
  }

bool operator< (const BigInteger& i_number_left, const BigInteger& i_number_right)
  {
  bool is_pos_left = i_number_left.IsPositive();
  bool is_pos_right = i_number_right.IsPositive();
  
  if ((!is_pos_left) && is_pos_right)
    return true;
  if (is_pos_left && (!is_pos_right))
    return false;

  if (i_number_left.GetDigitNumber() > i_number_right.GetDigitNumber())
    {
    if (is_pos_left)
      return false;
    else
      return true;
    }

  if (i_number_left.GetDigitNumber() < i_number_right.GetDigitNumber())
    {
    if (is_pos_left)
      return true;
    else
      return false;
    }

  size_t sz = i_number_left.GetDigitNumber();

  for (size_t i = 0; i < i_number_left.GetDigitNumber(); ++i)
    {
    if (i_number_left.GetDigit(sz - i - 1) < i_number_right.GetDigit(sz - i - 1))
      {
      if (is_pos_left)
        return true;
      else
        return false;
      }

    if (i_number_left.GetDigit(sz - i - 1) > i_number_right.GetDigit(sz - i - 1))
      {
      if (is_pos_left)
        return false;
      else
        return true;
      }
    }
  return false;
  }

bool operator> (const BigInteger& i_number_left, const BigInteger& i_number_right)
  {
  return i_number_right < i_number_left;
  }

bool operator<=(const BigInteger& i_number_left, const BigInteger& i_number_right)
  {
  return !(i_number_right < i_number_left);
  }

bool operator>=(const BigInteger& i_number_left, const BigInteger& i_number_right)
  {
  return i_number_right <= i_number_left;
  }

void BigInteger::_Swap(BigInteger& i_other)
  {
  swap(m_digits, i_other.m_digits);
  swap(m_sign, i_other.m_sign);
  }